package dfsketches.pathfind;

import java.util.HashSet;
import java.util.Hashtable;

import dfsketches.bicycles.BicycleQueue;
import dfsketches.bicycles.BicycleStack;

public class PathFinder {
	{
		masks = new int[32];
		int mask = 0x00000001;
		for (int i = 0; i < 32; i++) {
			masks[i] = mask;
			mask <<= 1;
		}
		deltaX[1] = deltaX[4] = deltaX[6] = -1;
		deltaX[3] = deltaX[5] = deltaX[8] = 1;
		deltaX[2] = deltaX[7] = 0;
		deltaY[1] = deltaY[2] = deltaY[3] = -1;
		deltaY[6] = deltaY[7] = deltaY[8] = 1;
		deltaY[4] = deltaY[5] = 0;
	}

	public PathFinder(int[][] map) {
		h = map.length;
		w = map[0].length;
		que = new BicycleQueue(w + h);
		this.map = map;
		temp = new int[h * w];
		pathes = new Hashtable<Integer, BicycleStack>();
	}
	
	//Breadth-first search
	public void findPath(int id, int x_from, int y_from, int x_to, int y_to) {
		for (int i = 0; i < w * h; i++) {
			temp[i] = -1;
		}
		
		int x = x_from;
		int y = y_from;
		temp[x * h + y] = -1;
		que.push(x * h + y);
		while (!(que.isEmpty() || x == x_to && y == y_to)) {
			int t = que.pop();
			x = t / h;
			y = t % h;
			for (int i = 1; i <= 8; i++) {
				t = (x + deltaX[i]) * h + y + deltaY[i];
				if ((map[y][x] & masks[i]) != 0 && temp[t] == -1) {
					que.push(t);
					temp[t] = x * h + y;
				}
			}
		}
		
		que.clear();
		
		BicycleStack path = new BicycleStack(w + h);
		int it = x_from * h + y_from;
		while (it != -1) {
			path.push(it);
			it = temp[it];
		}
		pathes.put(id, path);
	}
	
	public void removeUnreachable(int x, int y, HashSet<Integer> set) {
		for (int i = 0; i < w * h; i++) {
			temp[i] = 0;
		}

		temp[x * h + y] = 1;
		que.push(x * h + y);
		while (!(que.isEmpty())) {
			int t = que.pop();
			x = t / h;
			y = t % h;
			if (set.contains(t)) set.remove(t);
			for (int i = 1; i <= 8; i++) {
				t = (x + deltaX[i]) * h + y + deltaY[i];
				if ((map[y][x] & masks[i]) != 0 && temp[t] == 0) {
					que.push(t);
					temp[t] = 1;
				}
			}
		}
	}
	
	public int findClosest(int x, int y, HashSet<Integer> set) {
		for (int i = 0; i < w * h; i++) {
			temp[i] = 0;
		}

		temp[x * h + y] = 1;
		que.push(x * h + y);
		while (!(que.isEmpty())) {
			int t = que.pop();
			x = t / h;
			y = t % h;
			if (set.contains(t)) return t;
			for (int i = 1; i <= 8; i++) {
				t = (x + deltaX[i]) * h + y + deltaY[i];
				if ((map[y][x] & masks[i]) != 0 && temp[t] == 0) {
					que.push(t);
					temp[t] = 1;
				}
			}
		}
		return -1;
	}
	
	public int nextStep(int id) {
		if (pathes.get(id).isEmpty()) {
			pathes.remove(id);
			return -1;
		}
		return pathes.get(id).pop();
	}
	
	public void deletePath(int id) {
		pathes.remove(id);
	}
	
	private static int[] masks;
	private static int[] deltaX;
	private static int[] deltaY;
	
	private BicycleQueue que;
	private Hashtable<Integer, BicycleStack> pathes;
	private int[][] map;
	private int h;
	private int w;
	private int[] temp;

}